package suanfa.datastructure.tree;

public class ErfenBintree {
    public Binnode root;

    public ErfenBintree(){
        root=null;
    }

    public void add(int data){
        root=add(root,data);
    }
    public boolean find(int data){return find(root,data);}
    public void front(){
        firsttravel(root);
    }
    public int minimum(){
        return minimum(root).data;
    }
    public int maxmum(){
        return maxmum(root).data;
    }
    public int removemin(){
        int min=minimum();
        System.out.println("已删除最小值:"+min);
        removemin(root);
        return min;
    }
    public int removemax(){
        int max=maxmum();
        System.out.println("已删除最大值:"+max);
        removemin(root);
        return max;
    }
    public void remove(int data){
        System.out.println("已删除:"+data);
        remove(root,data);
    }
    private Binnode add(Binnode node, int data){
        if(node==null){
            return new Binnode(data);
        }

        if(data<node.data){
            node.left=add(node.left,data);
        }
        if(data>node.data){
            node.right=add(node.right,data);
        }
        return node;
    }

    private boolean find(Binnode node,int data){
        if(node==null){
            return false;
        }

        if(data<node.data){
            return find(node.left,data);
        }else if(data>node.data){
            return find(node.right,data);
        }else{
            return true;
        }
    }

    private void firsttravel(Binnode node){
        if(node==null){
            return;
        }
        System.out.println(node.data+"\t");
        if(node.left!=null){
            firsttravel(node.left);
        }
        if(node.right!=null){
            firsttravel(node.right);
        }
    }

    private  Binnode minimum(Binnode node){//查找最小值
        if(node.left==null){
            return node;
        }
        return minimum(node.left);

    }

    private Binnode maxmum(Binnode node){
        if(node.right==null){
            return node;
        }
        return maxmum(node.right);
    }

    private Binnode removemin(Binnode node){
        if(node.left==null){
            Binnode n=node.right;
            node.right=null;
            return n;
        }
        node.left=removemin(node.left);
        return node;
    }

    private Binnode removemax(Binnode node){
        if(node.right==null){
            Binnode n=node.left;
            node.left=null;
            return n;
        }
        node.right=removemax(node.right);
        return node;
    }
    private Binnode remove(Binnode node,int data){
        if(node==null){
            return null;
        }
        if(data<node.data){
            node.left=remove(node.left,data);
        }
        else if(data>node.data){
            node.right=remove(node.right,data);
        }else{
            if(node.left==null){
                Binnode n=node.right;
                node.right=null;
                return n;
            }
            if(node.right==null){
                Binnode n=node.left;
                node.right=null;
                return n;
            }
            Binnode s=minimum(node.right);
            s.right=removemin(node.right);
            s.left=node.left;
            node.left=node.right=null;
            return s;
        }
        return null;
    }
    public static void main(String[] args) {
        ErfenBintree t=new ErfenBintree();
        Binnode[] nodearr=new Binnode[10];
        int[] nums = { 5, 1, 6, 8, 3, 0, 7, 2, 9, 4 };
        for (int num : nums) {
            t.add(num);
        }
        t.removemin();
        t.removemax();
        t.remove(6);
        t.remove(2);
        t.front();

    }
}

class Binnode<E>{
     public  int data;
     public Binnode left ;
     public Binnode right ;
     public Binnode(int data){
        this.data=data;
    }



}
